import java.util.*;

public class SolutionInterview17_25 {

    public static class Trie {
        Trie[] tries = new Trie[26];

        void insert(String word) {
            Trie node = this;
            for (char c : word.toCharArray()) {
                if (node.tries[c - 'a'] == null) {
                    node.tries[c - 'a'] = new Trie();
                }
                node = node.tries[c - 'a'];
            }
        }

        boolean query(StringBuilder word) {
            Trie node = this;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                if (node.tries[c - 'a'] == null) {
                    return false;
                }
                node = node.tries[c - 'a'];
            }
            return true;
        }
    }

    int ans=0;
    List<String> re=new ArrayList<>();

    public String[] maxRectangle(String[] words) {
        Map<Integer, Set<String>> map=new HashMap<>();
        for (String word : words) {
            if (!map.containsKey(word.length())){
                map.put(word.length(),new HashSet<>());
            }
            map.get(word.length()).add(word);
        }
        Map<Integer,Trie> trieMap=new HashMap<>();
        for (Map.Entry<Integer, Set<String>> integerSetEntry : map.entrySet()) {
            trieMap.put(integerSetEntry.getKey(),new Trie());
            for (String s : integerSetEntry.getValue()) {
                trieMap.get(integerSetEntry.getKey()).insert(s);
            }
        }
        for (int i=1;i<=100;i++){
            for (int j=i;j<=100;j++){
                if (map.containsKey(i) && map.containsKey(j)){
                    List<String> l1=new ArrayList<>(map.get(j));
                    List<StringBuilder> check=new ArrayList<>();
                    for (int i1 = 0; i1 < j; i1++) {
                        check.add(new StringBuilder());
                    }
                    dfs(0,i,l1,trieMap.get(i), check);
                }
            }
        }
        String[] an=new String[re.size()];
        for (int i=0;i<re.size();i++){
            an[i]=re.get(i);
        }
        return an;
    }

    private void dfs(int k, int n, List<String> l1, Trie trie,List<StringBuilder> check) {
        if (k==n){
            if (ans<n*check.size()){
                ans=n*check.size();
                re=new ArrayList<>();
                for (StringBuilder stringBuilder : check) {
                    re.add(stringBuilder.toString());
                }
            }
            return;
        }
        for (int i=0;i<l1.size();i++){
            for (int j=0;j<check.size();j++){
                check.get(j).append(l1.get(i).charAt(j));
            }
            boolean flag=true;
            for (StringBuilder s : check) {
                if (!trie.query(s)) {
                    flag = false;
                    break;
                }
            }
            if (flag){
                dfs(k+1,n,l1,trie,check);
            }
            for (StringBuilder stringBuilder : check) {
                stringBuilder.deleteCharAt(stringBuilder.length() - 1);
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new SolutionInterview17_25().maxRectangle(new String[]{"this", "real", "hard", "trh", "hea", "iar", "sld"})));
    }
}
